package simple;

import java.util.HashMap;

/**
 * Description:实现 strStr() 函数。
 *
 * 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
 *
 * User: chengrongkai
 * Date: 2019-10-10
 * Time: 9:57
 */
public class Code_28 {
    /**
     * 滑动窗口
     * @param haystack
     * @param needle
     * @return
     */
    public static int strStr(String haystack, String needle) {
        int position = -1;
        if (null == haystack || null==needle || haystack.length()<needle.length()){
            return position;
        }
        if (haystack.length()==0||needle.length()==0){
            return 0;
        }
        for (int i = 0; i <= haystack.length()-needle.length(); i++) {
            int j=0;
            position = i;
            while(j<needle.length()){
                if (haystack.charAt(i+j) != needle.charAt(j++)){
                    position = -1;
                    break;
                }
            }
            if (position != -1){
                break;
            }

        }
        return position;
    }

    /**
     * kmp算法
     * @param haystack
     * @param needle
     * @return
     */
    public static int strStr1(String haystack, String needle) {
        int strLen = haystack.length(), subLen = needle.length();
        if (subLen == 0) return 0;
        if (strLen == 0) return -1;
        // 构建状态机
        int[][] FSM = new int[subLen][256];
        int X = 0, match = 0;
        for (int i = 0; i < subLen; i++) {
            match = (int) needle.charAt(i);
            for (int j = 0; j < 256; j++) {
                // 当前状态 + 匹配失败字符 = 孪生词缀状态 + 匹配字符
                FSM[i][j] = FSM[X][j];
            }
            FSM[i][match] = i + 1;
            if (i > 1) {
                // 下一孪生前缀状态 = X + match
                X = FSM[X][match];
            }
        }
        // 匹配子串
        int state = 0;
        for (int i = 0; i < strLen; i++) {
            state = FSM[state][haystack.charAt(i)];
            if (state == subLen) {
                return i - subLen + 1;
            }
        }
        return -1;
    }

    /**
     * kmp算法
     * @param haystack
     * @param needle
     * @return
     */
    public int strStr2(String haystack, String needle) {
        if (needle.length() == 0) {
            return 0;
        }
        char[] t = haystack.toCharArray();
        char[] p = needle.toCharArray();
        int i = 0; // 主串的位置
        int j = 0; // 模式串的位置
        int[] next = getNext(needle);
        while (i < t.length && j < p.length) {
            if (j == -1 || t[i] == p[j]) { // 当j为-1时，要移动的是i，当然j也要归0
                i++;
                j++;
            } else {
                // i不需要回溯了
                // i = i - j + 1;
                j = next[j]; // j回到指定位置

            }

        }

        if (j == p.length) {

            return i - j;

        } else {

            return -1;

        }
    }

    /**
     * 获取next数组
     * @param needle
     * @return
     */
    private int[] getNext(String needle){
        int len = needle.length();
        int[] pre = new int[len];
        pre[0] = -1;
        int k = -1;
        int j = 0;
        while (j < len-1){
            if (k == -1 || needle.charAt(k) == needle.charAt(j)){
                ++j;
                ++k;
                pre[j] = k;
            }else{
                k = pre[k];
            }
        }
        return pre;
    }


    public int strStr3(String haystack, String needle){
        if (needle.length() == 0){
            return 0;
        }
        int x=needle.length()-1,y=needle.length()-1;
        int index = -1;
        char[] charX = haystack.toCharArray();
        char[] charY = needle.toCharArray();
        HashMap<Character,Integer> map = new HashMap<>();
        for (int i = 0; i < charY.length; i++) {
            char c = charY[i];
            map.put(c,i);
        }
        while(y > 0 && x< haystack.length()){
            if (charX[x] == charY[y]){
                index = x;
                x--;
                y--;
            }else{
                index = -1;
                int subIndex = map.get(charX[x]) == null?-1:map.get(charX[x]);
                int badIndex = y - subIndex;
                x = x+badIndex;
                y = needle.length()-1;
            }
        }
        return index;
    }








    public static void main(String[] args) {
        String haystack = "abbacd";
        String needle = "acd";
        Code_28 code_28 = new Code_28();
        System.out.println(code_28.strStr3(haystack, needle));
    }







}


